package bin_tree;

import bin_tree.seachtree.BST;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

public class MyBinTree {
    private static class TreeNode {
        char val;
        //左右子树节点
        TreeNode left;
        TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
    }

    /**
     * 创建一个二叉树，返回根节点
     *
     * @return nodeA
     */
    public static TreeNode build() {
        TreeNode nodeA = new TreeNode('A');
        TreeNode nodeB = new TreeNode('B');
        TreeNode nodeC = new TreeNode('C');
        TreeNode nodeD = new TreeNode('D');
        TreeNode nodeE = new TreeNode('E');
        TreeNode nodeF = new TreeNode('F');
        TreeNode nodeG = new TreeNode('G');
        TreeNode nodeH = new TreeNode('H');
        nodeA.left = nodeB;
        nodeA.right = nodeC;
        nodeB.left = nodeD;
        nodeB.right = nodeE;
        nodeC.left = nodeF;
        nodeC.right = nodeG;
        nodeE.right = nodeH;
        return nodeA;
    }

    /**
     * 先序遍历；根左右
     * 传入一颗二叉树的根节点，就可以按照先序遍历的方式来输出节点值
     *
     * @param root
     */
    public static void preOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        //输出当前节点
        System.out.print(root.val + " ");
        //先递归访问左子树
        preOrder(root.left);
        //再递归访问右子树
        preOrder(root.right);
    }

    /**
     * 中序遍历；左根右
     * 传入一棵二叉树的根节点，就能按照中序遍历的方式来输出结果集
     *
     * @param root
     */
    public static void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        //先递归访问左子树
        inOrder(root.left);
        //第二次访问该节点，输出节点
        System.out.print(root.val + " ");
        //再递归访问右子树
        inOrder(root.right);
    }

    /**
     * 中序遍历；左右根
     * 传入一棵二叉树的根节点，就能按照后序遍历的方式来输出结果集
     *
     * @param root
     */
    public static void postOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        //先递归访问左子树
        postOrder(root.left);
        //再递归访问右子树
        postOrder(root.right);
        //第三次访问当前节点，输出节点
        System.out.print(root.val + " ");
    }

    /**
     * 层序遍历输出二叉树节点.用队列来解决问题
     *
     * @param root
     */
    public static void leveOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        //此时树不为空，将根节点入队
        queue.offer(root);
        while (!queue.isEmpty()) {
            //取出队首元素
            TreeNode cur = queue.poll();
            //输出队首元素的的值
            System.out.print(cur.val + " ");
            //当前节点还有子节点，将子节点从左到右依次入队
            if (cur.left != null) {
                queue.offer(cur.left);
            }
            if (cur.right != null) {
                queue.offer(cur.right);
            }
        }
    }

    /**
     * 传入一颗二叉树的根节点，就能统计出当前二叉树中一共有多少个节点，返回节点数
     * 此时的访问就不再是输出节点值，而是计数器 + 1操作
     *
     * @param root
     * @return 当前二叉树的节点个数
     */
    public static int getNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return 1 + getNodes(root.left) + getNodes(root.right);
    }

    /**
     * 使用层序遍历来统计当前树中的节点个数
     *
     * @param root
     * @return 节点个数
     */
    public static int getNodesNonRecursion(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int size = 0;
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            //统计当前节点
            size++;
            if (cur.left != null) {
                queue.offer(cur.left);
            }
            if (cur.right != null) {
                queue.offer(cur.right);
            }
        }
        return size;
    }

    /**
     * 传入一颗二叉树的根节点，就能统计出当前二叉树的叶子结点个数
     *
     * @param root
     * @return 叶子节点数
     */
    public static int getLeafNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        return getLeafNodes(root.left) + getLeafNodes(root.right);
    }

    /**
     * 使用层序遍历来统计叶子结点的个数
     *
     * @param root
     * @return 叶子节点数size
     */
    public static int getLeafNodesNonRecursion(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int size = 0;
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if (cur.left == null && cur.right == null) {
                size++;
            }
            if (cur.left != null) {
                queue.offer(cur.left);
            }
            if (cur.right != null) {
                queue.offer(cur.right);
            }
        }
        return size;
    }

    /**
     * 判断当前以root为根节点的二叉树中是否包含指定元素val，
     * 若存在返回true，不存在返回false
     *
     * @param val
     * @return 是否存在查询节点
     */
    public static boolean contains(TreeNode root, char val) {
        if (root == null) {
            return false;
        }
        if (root.val == val) {
            return true;
        }
        return contains(root.left, val) || contains(root.right, val);
    }

    /**
     * 传入一个以root为根节点的二叉树，就能求出该树的高度
     *
     * @param root
     * @return 树的高度
     */
    public static int height(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return 1 + Math.max(height(root.left), height(root.right));
    }

    /**
     * 求出以root为根节点的二叉树第k层的节点个数
     *
     * @param root
     * @param k
     * @return k层节点数
     */
    public static int getKLevelNodes(TreeNode root, int k) {
        if (root == null || k <= 0) {
            return 0;
        }
        //当k减到1时，说明走到了该层节点
        if (k == 1) {
            return 1;
        }
        return getKLevelNodes(root.left, k - 1) + getKLevelNodes(root.right, k - 1);
    }

    public static String toString(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        generateBSTString(root, 0, sb);
        return sb.toString();
    }

    /**
     * 先序遍历以root为根的BST，将节点值存储在sb中
     *
     * @param root
     * @param height
     * @param sb
     */
    private static void generateBSTString(TreeNode root, int height, StringBuilder sb) {
        if (root == null) {
            sb.append(generateHrightStr(height)).append("NULL\n");
            return;
        }
        sb.append(generateHrightStr(height)).append(root.val).append("\n");
        generateBSTString(root.left, height + 1, sb);
        generateBSTString(root.right, height + 1, sb);
    }

    /**
     * 按照当前所处的树的层次打印 --
     * 每多一层，就多两个--
     *
     * @param height
     * @return
     */
    private static String generateHrightStr(int height) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < height; i++) {
            sb.append("--");
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        TreeNode root = build();
        System.out.println("前序遍历的结果为:");
        preOrder(root);
        System.out.println();
        System.out.println("中序遍历的结果为:");
        inOrder(root);
        System.out.println();
        System.out.println("后序遍历的结果为:");
        postOrder(root);
        System.out.println();
        System.out.println("层序遍历的结果为:");
        leveOrder(root);
        System.out.println();
        System.out.println("当前二叉树一共有:" + getNodes(root) + "个节点数");
        System.out.println("当前二叉树一共有:" + getNodesNonRecursion(root) + "个节点数");
        System.out.println("当前二叉树一共有:" + getLeafNodes(root) + "个叶子节点数");
        System.out.println("当前二叉树一共有:" + getLeafNodesNonRecursion(root) + "个叶子节点数");
        System.out.println(contains(root, 'E'));
        System.out.println(contains(root, 'P'));
        System.out.println("当前二叉树的高度为:" + height(root));
        System.out.println("当前二叉树第3层的节点个数为:" + getKLevelNodes(root, 3));
        System.out.println(toString(root));
    }
}
